package leetcode_800;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 *@author 周杨
 *SpecialBinaryString_761 一个特殊的二进制字符串就是括号字符串 任何前缀1的个数都不少于0 试图移动一个特殊二进制字符串里的任意两个特殊二进制子串 问返回的最大特殊二进制字符串的按字典顺序大小是什么
 *describe:用递归 典型的子问题优化构成全局最优解 AC 87%
 *2018年10月18日 上午11:19:56
 */
public class SpecialBinaryString_761 {
	
	 public static void main(String[] args) {
		 SpecialBinaryString_761 test=new SpecialBinaryString_761();
		 System.out.println(test.makeLargestSpecial("11011000"));
	}
	
	 public String makeLargestSpecial(String S) {
	       int count = 0, i = 0;
	        List<String> res = new ArrayList<String>();
	        for (int j = 0; j < S.length(); ++j) {
	          if (S.charAt(j) == '1') count++;
	          else count--;
	          if (count == 0) {//因为合法的串必须以1开头 0结尾 开始递归 找出子问题的最优解
	            res.add('1' + makeLargestSpecial(S.substring(i + 1, j)) + '0');
	            i = j + 1;
	          }
	        }
	        Collections.sort(res, Collections.reverseOrder());//把1放前面
	        return String.join("", res);//把子问题所有的解连接起来
	    }
}
